package com.jack.algorithm;

/**
 * Created by zhang_j on 2020/7/17
 */
public class quicksort {

    public static void main(String[] args) {
        int[] a = {9, 8, 7, 6, 5, 1, 2, 3};
        quicksort1(a, 0, a.length - 1);
        for (int i : a) {
            System.out.print(i + ",");
        }
    }

    private static void quicksort1(int[] nums, int begin, int end){
        if(begin >= end){
            return;
        }
        int i = begin, j = end, num = nums[begin];
        while(i < j){
            while(i < j && nums[j] > num){
                j--;
            }
            if(i < j){
                nums[i++] = nums[j];
            }
            while(i < j && nums[i] < num){
                i++;
            }
            if(i < j){
                nums[j--] = nums[i];
            }
        }
        nums[i] = num;
        quicksort1(nums, begin, i-1);
        quicksort1(nums, i+1, end);
    }










    private static void quicksort(int[] nums, int l, int r) {
        if (l >= r) {
            return;
        }
        int i = l, j = r, x = nums[l];
        while (i < j) {
            while (i < j && nums[j] >= x) {
                j--;
            }
            if(i < j){
                nums[i++] = nums[j];
            }
            while(i < j && nums[i] < x){
                i++;
            }
            if(i < j){
                nums[j--] = nums[i];
            }
        }
        nums[i] = x;
        quicksort(nums, l, i-1);
        quicksort(nums, i+1, r);
    }
}
